//给你两个下标从 0 开始的整数数组 nums 和 divisors 。 
//
// divisors[i] 的 可整除性得分 等于满足 nums[j] 能被 divisors[i] 整除的下标 j 的数量。 
//
// 返回 可整除性得分 最大的整数 divisors[i] 。如果有多个整数具有最大得分，则返回数值最小的一个。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [4,7,9,3,9], divisors = [5,2,3]
//输出：3
//解释：divisors 中每个元素的可整除性得分为：
//divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 5 整除。
//divisors[1] 的可整除性得分为 1 ，因为 nums[0] 能被 2 整除。 
//divisors[2] 的可整除性得分为 3 ，因为 nums[2]、nums[3] 和 nums[4] 都能被 3 整除。 
//因此，返回 divisors[2] ，它的可整除性得分最大。
// 
//
// 示例 2： 
//
// 
//输入：nums = [20,14,21,10], divisors = [5,7,5]
//输出：5
//解释：divisors 中每个元素的可整除性得分为：
//divisors[0] 的可整除性得分为 2 ，因为 nums[0] 和 nums[3] 都能被 5 整除。
//divisors[1] 的可整除性得分为 2 ，因为 nums[1] 和 nums[2] 都能被 7 整除。
//divisors[2] 的可整除性得分为 2 ，因为 nums[0] 和 nums[3] 都能被5整除。 
//由于 divisors[0]、divisors[1] 和 divisors[2] 的可整除性得分都是最大的，因此，我们返回数值最小的一个，即 
//divisors[2] 。
// 
//
// 示例 3： 
//
// 
//输入：nums = [12], divisors = [10,16]
//输出：10
//解释：divisors 中每个元素的可整除性得分为：
//divisors[0] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 10 整除。
//divisors[1] 的可整除性得分为 0 ，因为 nums 中没有任何数字能被 16 整除。 
//由于 divisors[0] 和 divisors[1] 的可整除性得分都是最大的，因此，我们返回数值最小的一个，即 divisors[0] 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length, divisors.length <= 1000 
// 1 <= nums[i], divisors[i] <= 10⁹ 
// 
//
// Related Topics 数组 👍 15 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
 * @author ldltd
 * @date 2024-05-18 12:45:23
 * @description 2644.找出可整除性得分最大的整数
 */
public class FindTheMaximumDivisibilityScore{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 FindTheMaximumDivisibilityScore fun=new FindTheMaximumDivisibilityScore();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int maxDivScore(int[] nums, int[] divisors) {
		int res=divisors[0];
		int count=-1;
		int t=0;
		int i,j;
		for ( i = 0; i < divisors.length; i++) {
			t=0;
			for ( j = 0; j < nums.length; j++) {
				if(nums[j]%divisors[i]==0)
					t++;
			}
			if(t>=count) {
				if(t==count&&divisors[i]>res)
					continue;
				count=t;
				res=divisors[i];
			}
		}
		return res;
    }


	/*优化1，小于divisor的无法被其整除
	* 对num排序，只遍历大于divisor i的
	*
	* 优化2  最大的cnt 最大重复次数 dup (maxCnt-dup+1)*d>=max(nums)
	* maxCnt>max(nums)/d+dup,无法拿到最大的时候直接结束
	* 比如 3 3 3 2 1 1
	* maxCnt=3,dup=3,  把d升序排列，如果前面的d满足，则后面的也一定满足
	* 因为num也是升序排列的，最大的
	* */

	public int maxDivScore1(int[] nums, int[] divisors) {
		Arrays.sort(nums);
		int n=nums.length;
		int dup=0;
		for (int i = 1; i < n; i++) {
			if(nums[i]==nums[i-1]){
				dup++;
			}
		}
		Arrays.sort(divisors);

		int res=0;
		int maxCnt=-1;
		for (int d : divisors) {
			if(maxCnt-dup>=nums[n-1]/d){
				break;
			}
			int cnt=0;
			for (int i = n-1; i >=0 ; i--) {
				int x=nums[i];
				if(x<d) break;
				if(x%d==0) cnt++;
			}
			if(cnt>maxCnt){
				maxCnt=cnt;
				res=d;
			}
		}
		return  res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
